/*
The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.
*/

class Solution {
public:
    // Reversal cantor expansion:
    //      num = {a1*(n-1)! + a2*(n-2)! + ... + a^n-1*1! + an} + 1
    string getPermutation(int n, int k) {
        if (n < 2) return string("1");
        vector<int> res;
        set<int> numbers;
        for (int i = 1; i <= n; i++) numbers.insert(i);
        k--;
        for (int tmpint = n; tmpint > 0; tmpint--) {
            int factorial = fac(tmpint-1);
            int coefficient = k / factorial;
            k = k % factorial;
            // find element which is greater than $coefficient elements
            auto it = numbers.begin();
            for (; coefficient > 0; it++, coefficient--) ;
            res.push_back(*it);
            numbers.erase(it);
        }
        // translate to string
        string s(n, '0');
        for (int i = 0; i < n; i++) {
            s[i] += res[i];
        }
        return s;
    }
private:
    int fac(int n) {
        int res = 1;
        for (int i = 2; i <= n; i++) {
            res *= i; // 1*2*.. *n
        }
        return res;
    }
};
